let minDistance = function (s1, s2) {
    let m = s1.length, n = s2.length;

    // 初始化一个 (m+1) * (n+1)大小的数组
    let dp = new Array(m + 1);
    for (let i = 0; i < m + 1; i++) {
        dp[i] = new Array(n + 1).fill(0)
    }

    for (let i = 1; i <= m; i++) {
        dp[i][0] = i;
    }

    for (let j = 1; j <= n; j++)
        dp[0][j] = j;

    // 自底向上求解
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i - 1] === s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1]
            else
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,  //  删除
                    dp[i][j - 1] + 1,       // 插入
                    dp[i - 1][j - 1] + 1     // 替换
                )
        }
    }
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
};


let minDistance01 = function (word1, word2) {
    let m = Math.max(word1.length, word2.length)
    let n = Math.min(word1.length, word2.length)

    // 初始化一个 (m+1) * (n+1)大小的数组
    let dp = new Array(m + 1)

    // dp[0...n]的初始值
    for (let j = 0; j <= n; j++)
        dp[j] = j;

    // dp[j] = min(dp[j-1], pre, dp[j]) + 1
    for (let i = 1; i <= m; i++) {
        let temp = dp[0];
        // 相当于初始化
        dp[0] = i;
        for (let j = 1; j <= n; j++) {
            // pre 相当于之前的 dp[i-1][j-1]
            let pre = temp;
            temp = dp[j];
            // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
            if (word1[i - 1] === word2[j - 1]) {
                dp[j] = pre;
            } else {
                dp[j] = Math.min(Math.min(dp[j - 1], pre), dp[j]) + 1;
            }
        }
    }

    return dp[n];
};

minDistance01("apple", "rad")
